package org.chnxi.study.leetcode.questions50.ques32;

import java.util.Stack;

/**
 * 官方解
 * 使用stack的方式
 */
public class Simple01 {

    public static void main(String[] args) {
        String s = "()()()";
        System.out.println(longestValidParentheses(s));
    }

    public static int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        //假设从最左端开始的括号是有效的
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            // 遇左括号，将左括号压入栈
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                // 遇右括号，将前一个弹出栈
                stack.pop();
                //如果栈为空，将当前索引位压入栈，假设下一个括号为有效
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    //计算最大有效程度
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }


}
